package com.colter.project.data.structure.sort;

import java.util.ArrayList;
import java.util.List;

public class BucketSort {
	public static void main(String[] args) {
		int[] nums = new int[] { 5, 0, 8, 11, 15, 55, 45, 30, 22, 99, 65 };
		sort(nums);
	}

	public static int[] sort(int[] nums) {
		List<ArrayList<Integer>> list = new ArrayList<>();
		for (int i = 0; i < 10; i++) {
			list.add(new ArrayList<Integer>());
		}

		int min = getMin(nums);
		int max = getMax(nums);

		int divide = (max - min) / 9;

		for (int i = 0; i < nums.length; i++) {
			int target = (nums[i] - min) / divide;
			list.get(target).add(nums[i]);
		}

		for (int i = 0; i < list.size(); i++) {
			List<Integer> temp = list.get(i);
			int[] resultTemp = InsertionSort.sort(listToArray(temp));
			ArrayList<Integer> result = new ArrayList<>();
			for (int j = 0; j < resultTemp.length; j++) {
				result.add(resultTemp[j]);
			}
			list.set(i, result);
		}

		for (int i = 0; i < list.size(); i++) {
			ArrayList<Integer> temp = list.get(i);
			for (int j = 0; j < temp.size(); j++) {
				System.out.println(temp.get(j));
			}

		}

		return nums;
	}

	public static int[] listToArray(List<Integer> list) {
		int[] result = new int[list.size()];
		for (int i = 0; i < result.length; i++) {
			result[i] = list.get(i);
		}
		return result;
	}

	public static int getMax(int[] nums) {
		int max = nums[0];
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] > max) {
				max = nums[i];
			}
		}
		return max;
	}

	public static int getMin(int[] nums) {
		int min = nums[0];
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] < min) {
				min = nums[i];
			}
		}
		return min;
	}
}
